package com.wh;

/**
 * @Description test
 * @Author zhq
 * @Date 2024-12-18
 *
 * 三种类型硬币 一分钱两分钱五分钱的硬币  随意出个金额 要求以最少的硬币数来获取这个金额   采用递归的方式
 */

import org.junit.jupiter.api.Test;


public class test {

    public static int coinChange(int amount){
        int[] coins = {5,2,1};
        return helper(amount,0,coins);
    }
    private static int helper(int n,int index, int[] coins){
        //金额凑齐了  返回0
        if(n == 0){
            return 0;
        }
        if(n <0 || index >= coins.length){
            return Integer.MAX_VALUE;
        }
        int take = 0;
        int result = helper(n-coins[index],index,coins);
        if (result != Integer.MAX_VALUE){
            take = 1 + result;
        }
        //不选择这个硬币
        int skip = helper(n,index+1,coins);
        //返回 使用数量小的那个
        return Math.min(take,skip);
    }
    public static void main(String[] args) {
        int amount = -1;
        int result = coinChange(amount);
        System.out.println("凑出金额" + amount + "最少需要" + result);
    }
}

